package com.demo.java.OD451_500.OD462;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【汽车初始油量 ，智能驾驶(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146350596
 */
public class OdMain {
    public static int m;  // 地图的行数
    public static int n;  // 地图的列数
    public static int min = Integer.MAX_VALUE;  // 记录最小油量消耗，初始值为最大整数

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取地图的行数和列数
        String[] size = scanner.nextLine().split(",");
        m = Integer.parseInt(size[0]);
        n = Integer.parseInt(size[1]);

        int[][] map = new int[m][n];  // 创建一个二维数组表示地图

        // 读取地图的油量信息
        for (int i = 0; i < m; i++) {
            String[] rowValues = scanner.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(rowValues[j]);
            }
        }

        // 执行广度优先搜索算法
        bfs(map);

        // 输出结果：如果无法到达目的地，输出-1，否则输出最小油量
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }

    // 广度优先搜索算法
    private static void bfs(int[][] map) {
        Queue<int[]> queue = new LinkedList<>();  // 用队列存储待处理的状态
        // 起点为地图右下角，油量为map[m-1][n-1]，步数为0
        int[] start = {m - 1, n - 1, map[m - 1][n - 1], 0};
        queue.add(start);  // 将起点加入队列
        map[m - 1][n - 1] = 0;  // 设置起点已访问

        // 队列不为空时继续处理
        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 取出队列的第一个元素
            int row = current[0];  // 当前行
            int col = current[1];  // 当前列
            int count = current[2];  // 当前油量
            int steps = current[3];  // 当前步数

            // 如果当前油量大于100，则跳过该状态
            if (count > 100) {
                continue;
            }

            // 如果到达左上角 (0,0)，则更新最小油量消耗
            if (row == 0 && col == 0) {
                count += map[0][0];  // 加上目标点的油量
                if (count <= 100) {  // 如果油量不超过100，更新最小油量
                    min = Math.min(min, count);
                }
                continue;  // 继续处理队列中的其他状态
            }

            // 向上、下、左、右四个方向扩展
            exploreDirection(queue, row - 1, col, map, count, steps + 1);  // 向上
            exploreDirection(queue, row + 1, col, map, count, steps + 1);  // 向下
            exploreDirection(queue, row, col - 1, map, count, steps + 1);  // 向左
            exploreDirection(queue, row, col + 1, map, count, steps + 1);  // 向右
        }
    }

    // 探索一个方向（上下左右四个方向中的一个）
    private static void exploreDirection(Queue<int[]> queue, int row, int col,
                                         int[][] map, int count, int steps) {
        // 判断新的位置是否合法（在地图内，且未被访问过）
        if (row >= 0 && row < m && col >= 0 && col < n && map[row][col] != 0) {
            int num = map[row][col];  // 当前位置的油量
            map[row][col] = 0;  // 标记该位置已访问

            // 创建新的状态，存入队列
            int[] next = {row, col, num == -1 ? 0 : count + num, steps};
            queue.add(next);

            map[row][col] = 0;  // 重置该位置已访问状态
        }
    }
}
